package find;

import java.util.Scanner;

//AC  这道题有点不同，就是
//ADA
//ADADADA
//返回的是3
public class TestKmp {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		scanner.nextLine();
		String pattern = "";
		String string = "";
		for (int i = 1; i <= testCase; i++) {
			pattern = scanner.nextLine();
//			scanner.nextLine();
			string = scanner.nextLine();
			System.out.println(kmp(string, pattern));
		}
		scanner.close();
	}

	public static int kmp(String string, String stringPattern) {
		if (string == null || stringPattern == null) {
			return stringPattern == string ? 0 : -1;
		}
		char[] chars = string.toCharArray();
		char[] pattern = stringPattern.toCharArray();
		int[] next = new int[pattern.length];
		getNext(pattern, next);
		int k = 0, count = 0;
		for (int i = 0; i < chars.length; i++) {
			while (k > 0 && pattern[k] != chars[i]) {
				k = next[k - 1];
			}
			if (pattern[k] == chars[i]) {
				k++;
			}
			if (k == pattern.length) {
				count++;
				k = next[k - 1];  //所以我这里用了next[k - 1]
			}
		}
		return count;
	}

	public static void getNext(char[] pattern, int[] next) {
		if (pattern == null) {
			return ;
		}
		next[0] = 0;
		int index = 1, k = 0; // k表示最大前缀和后缀长度
		while (index < pattern.length) {
			while (k > 0 && pattern[k] != pattern[index]) {
				k = next[k - 1];
			}
			if (pattern[k] == pattern[index]) {
				k++;
			}
			next[index] = k;
			index++;
		}
	}
}
